﻿/*
题目: 出租车的最大盈利

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。

乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ，愿意支付 tipi 元的小费。

每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。

给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。

注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。

https://leetcode.cn/problems/maximum-earnings-from-taxi/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 动态规划
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        int sz = rides.size();
        // dp[i] 表示完成第 i 个任务的最大盈利
        vector<long long> dp(sz, 0L);

        // 结束时间升序，开始时间升序，必须先按结束时间来排序，方便二分查找
        ::sort(rides.begin(), rides.end(), [](auto& x, auto& y) {
            if (x[1] == y[1])   return x[0] < y[0];
            return x[1] < y[1];
            });

        dp[0] = profit(rides[0]);
        for (int i = 1; i < sz; i++) {
            // 这个任务选择排在 第一个小于 i 任务的后面 
            int his = bin_search(rides, start(rides[i]), 0, i - 1);
            if (his == -1) {   // 没有这样的任务
                dp[i] = max(dp[i - 1], (long long)profit(rides[i]));
            }
            else {
                dp[i] = max(dp[i - 1], dp[his] + profit(rides[i]));
            }
        }

        return dp[sz - 1];
    }

    // 第一个 < tar 的
    int bin_search(vector<vector<int>>& rides, int tar, int left, int right) {
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (end(rides[mid]) > tar) {
                right = mid - 1;
            }
            else {      // end(rides[mid]) <= tar
                left = mid + 1;
            }
        }
        return left - 1;
    }

    int start(const vector<int>& ar) {
        return ar[0];
    }

    int end(const vector<int>& ar) {
        return ar[1];
    }

    int profit(const vector<int>& ar) {
        return ar[1] - ar[0] + ar[2];
    }
};